home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d16 / winvn060.arc / SHELLSOR.C < prev    next >
C/C++ Source or Header  |  1991-07-01  |  3KB  |  70 lines
  1.  
  2. /* Shellsort is a variation on Insertion Sort that is virtually unbeatable 
  3.  * on small data sets.  Insertion Sort is slow because it only exchanges 
  4.  * adjacent elements.  Shellsort circumvents this by allowing the exchange 
  5.  * of elements that are farther apart.  It works by first performing Insertion 
  6.  * Sort on subsets of the data.  For example, Shellsort might first sort 
  7.  * the set of elements 1, 6, 11, 16... relative to each other--the effect 
  8.  * is that the elements in that subset are moved much closer to their final 
  9.  * positions.  At first the sets are wide-spread, perhaps every fortieth 
  10.  * element.  Then it repeats using a tighter set, perhaps every fourteenth 
  11.  * element, then every fourth element.  Each of these passes is much cheaper 
  12.  * than a traditional Insertion Sort pass.  The effect of the passes is that 
  13.  * the data set is mutated to be in "almost sorted" order.  The final insertion 
  14.  * sort pass can then go very quickly because insertion sort does very well on 
  15.  * almost sorted data.  In other words, at first the elements take large leaps 
  16.  * to the general location they belong and successively smaller steps move the 
  17.  * element to its precise place. I call this algorithm "inscrutable sort" 
  18.  * because even after having coded the algorithm, I still have trouble 
  19.  * following the animation.  No one has been able to analyze this algorithm 
  20.  * rigorously; the functional form of the running time is conjectured to be 
  21.  * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general 
  22.  * purpose sort since it has excellent performance and the code you must write 
  23.  * is only slightly more complex than Insertion Sort.
  24.  *
  25.  * Author: Julie Zelenski, NeXT Developer Support
  26.  * You may freely copy, distribute and reuse the code in this example.  
  27.  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
  28.  * its fitness for any particular use.      qsort
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <string.h>
  33.  
  34. #define memSwap(a,b,unused) tmp = *(char far * far *)(a); \
  35.   *(char far * far *)(a) = *(char far * far *)(b); *(char far * far *)(b) = tmp;
  36.  
  37.  
  38. void _FAR_ _cdecl
  39. ShellSort(base, nElements, width, compare)
  40. void far *base;
  41. size_t nElements;
  42. size_t width;
  43. int (_FAR_ _cdecl *compare)( const void far *elem1, const void far *elem2 );
  44. {
  45. #define STRIDE_FACTOR 3
  46.    int c,d, stride;
  47.    char far *tmp;
  48.    int found;
  49.  
  50.    stride = 1;
  51.    while (stride <= nElements) stride = stride*STRIDE_FACTOR +1;
  52.     
  53.    while (stride>(STRIDE_FACTOR-1)) {
  54.         stride = stride / STRIDE_FACTOR;
  55.        for (c = stride; c < nElements; c++){
  56.           found = 0;
  57.           d = c-stride;
  58.           while ((d >= 0) && !found) {
  59.              if (compare((char far *)base+(d+stride)*width, (char far *)base+d*width) < 0) {
  60.                memSwap((char far *)base+(d+stride)*width,(char far *)base+d*width,width);
  61.                  d -= stride;
  62.               } else {
  63.                  found = 1;
  64.             }
  65.           }
  66.        }
  67.    }
  68. }
  69.     
  70.